import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-11-27
 * Time: 20:01
 */
public class Binarysearchsorting {
    public static int search(int[] arr, int left, int right, int key) {
        if (left > right) {
            // 没有找到key，返回应该插入的位置
            return left;
        }
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] > key) {
            return search(arr, left, mid - 1, key);
        } else {
            return search(arr, mid + 1, right, key);
        }
    }

    public static void sort(int[]arr){
        //遍历比较
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<arr[i-1]){
                //进入二分查找
                int pos=search(arr,0,i-1,arr[i]);
                //目标位置集体往后移
                int tmp=arr[i];
                for(int j=i-1;j>=pos;j--){
                    arr[j+1]=arr[j];
                }
                //插入
                arr[pos]=tmp;
            }
            System.out.println("第"+i+"次: "+Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,56,88,66,35,2,8};
        sort(arr);
    }
}
